Doit 자료구조와 함께 배우는 알고리즘 기초 파이썬 편

0016 swjungle 🤖의 일환으로 학습한 자료를 정리한 문서입니다.


Chapter02 기본 자료구조와 배열


for문 끝나자마자 else가 나타나는 것은 처음 봤다. Why does python use 'else' after for and while loops

어쨌든 소수를 찾을때엔 primes의 모든 원소를 찾아야 하니 Π(N)정도의 시간이 걸린다. Prime Counting Function 참고{wiki} 조금만 더 최적화를 한다면 굳이 primes의 모든 원소를 찾을 필요는 없고, 제곱근 정도의 시간만 소요되게 만들 수 있겠다. 그리고 MAX까지 달려갈 때 모든 짝수를 제외할 수 있으므로.... 전체적으로 보았을 때 대충..

O(Π(N)2N2)=O(NΠ(N))

이...렇......게? 되려나? Π가 대충 로그정도의 속도를 가지고 있다고 하니까 조금만 더 멍청하게 생각한다면 O(NlogN) 정도.....?? 그냥 에라토스테네스의 체를 사용해서 메모리는 많이 먹어도 O(N)에 끝내는 방법이 더 현명해 보이기도 하지만 일단 머리속에 입력은 해두자.

Chapter03 검색 알고리즘 :: 이진검색 / 이분검색

이분탐색 헷갈리지 않게 구현하기 {최백준}

binary search를 활용한 lower upper bound 그리고 parametric search까지

파이썬에선 index() 함수로 리스트, 튜플 내 원소 검색을 수행할 수 있다.

Chapter05 재귀 알고리즘

문제풀이는 전부 algorithms 페이지에서 진행함.

8개의 퀸이 서로를 잡을 수 없도록 8 * 8 체스판에 배치하시오

Chapter06 정렬 알고리즘

Chapter04 스택과 힙

Chapter09 트리

tree 기초
graph 기초